Re: Non-PK encryption not vulnerable via low key length?!
der Mouse (mouse@Collatz.McRCIM.McGill.EDU)
Thu, 16 Mar 1995 07:09:24 -0500
>> Correct me if I am wrong - RC2 and RC4 are not public key
>> cyrptosystems, and hence are not "prone" to the problems with low
>> moduli.
> You are wrong.
They _are_ public-key cryptosystems??
> If the key is only 128-bit, that's a much smaller keyspace to
> brute-force attack than a 1024-bit key.
True as far as it goes...but I think you're missing the point.
If you're trying to attack a 1024-bit public RSA key, this is on a par
with the difficulty of factoring a 1024-bit number. This is much
easier than brute-forcing a 1024-bit secret key - I don't know how hard
factoring is nowadays, but I'm quite certain it's a hell of a lot
easier than just making random guesses. A good private-key cipher
presents essentially that problem: guessing a private value with no
information to go on. Thus, if DES were ideal in this respect[%],
there would be no better way to crack it than trying one 56-bit key
after another until you find the one that produces sense rather than
nonsense upon decryption of the message[$]. Expected work: 2^55
attempts. If we assume RC4 is ideal[#], the expected work to crack it
in this use (ie, 128-bit key) is 2^127 encryptions.
[%] DES isn't ideal for various reasons. It is known to have some weak
keys, there is an attack known that (if memory serves) allows
breaking it with 2^47 known plaintexts, and another that works with
2^47 chosen plaintexts. Still, 2^47 is a lot of work.
[$] Telling sense from nonsense is another problem entirely, and is one
reason why it's always a good idea to compress your data before
encrypting it.
[#] I have no idea how close to true this is, and given RC4's recency
in the public world, I doubt anyone else who can talk does either.
Key size comparisons between cryptosystems should be taken with a large
handful of salt, at least until you've looked carefully at what
breaking those keys entails.
der Mouse
mouse@collatz.mcrcim.mcgill.edu